﻿#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
using namespace std;

//1047. 删除字符串中的所有相邻重复项
class Solution {
public:
    string removeDuplicates(string s)
    {
        string st;
        for (const auto& c : s)
        {
            if (!st.empty() && c == st.back())
            {
                st.pop_back();
            }
            else
                st.push_back(c);
        }
        return st;
    }
};


//844.⽐较含退格的字符串
class Solution {
public:
    bool backspaceCompare(string s, string t)
    {
        string rets, rett;
        for (const auto& c : s)//else与最近的同作用域下的if匹配
        {
            if (c == '#')
            {
                if (!rets.empty()) rets.pop_back();
            }

            else rets += c;
        }
        cout << rets;
        for (const auto& c : t)
        {
            if (c == '#')
            {
                if (!rett.empty()) rett.pop_back();
            }

            else rett += c;
        }

        return rets == rett ? true : false;
    }
};


//227. 基本计算器 II(栈的使用)
class Solution {
public:
    int calculate(string s)
    {
        //减法和除法的left与right的顺序
        stack<int> nums;
        stack<char> opers;
        int tmp = 0;//求和数字
        char op;
        //直接将乘除法算完，并将减法的操作转换成+(-num)
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == ' ') continue;
            else if (s[i] >= '0' && s[i] <= '9')
            {
                while (s[i] >= '0' && s[i] <= '9' && i < s.size())
                {
                    tmp = tmp * 10 + (s[i++] - '0');//防止越界，括号括起来后部分
                }
                i--;
                if (!opers.empty() && opers.top() == '-')
                    nums.push(-tmp);
                else
                    nums.push(tmp);
                tmp = 0;

                if (!opers.empty())
                {
                    if (opers.top() == '*')
                    {
                        opers.pop();
                        int left = nums.top();
                        nums.pop();
                        int right = nums.top();
                        nums.pop();
                        nums.push(left * right);
                    }
                    else if (opers.top() == '/')
                    {
                        opers.pop();
                        int left = nums.top();
                        nums.pop();
                        int right = nums.top();
                        nums.pop();
                        nums.push(right / left);
                    }
                }

            }
            else
                opers.push(s[i]);

        }

        int ret = 0;
        while (!nums.empty())
        {
            ret += nums.top();
            nums.pop();
        }
        return ret;
    }
};
